我們知道要優化一個動態規劃問題，可以從兩個方向下手，一個是使用Memo把已經找過的答案存起來，另外一個就是使用DP Table

我們先從比較簡單的部分開始，使用一個Memo很簡單，直接加上就好

fun minDistanceWithMemo(s1: String, s2: String): Int {
    val memo = HashMap<Pair<Int,Int>,Int>()//使用Memo存下走過的

    fun dp(i: Int, j: Int): Int {
        if(memo.containsKey(Pair(i,j))){//在開始之前先去memo查找看看
            return memo[Pair(i,j)]!!
        }
        if (i == -1) return j + 1
        if (j == -1) return i + 1

        return if (s1[i] == s2[j]) {
            dp(i - 1, j - 1)
        } else {
            val insert = dp(i, j - 1) + 1
            val delete = dp(i - 1, j) + 1
            val replace = dp(i - 1, j - 1) + 1
            memo[Pair(i,j)] = insert.coerceAtMost(delete).coerceAtMost(replace)
            return memo[Pair(i,j)]!!
        }
    }
    return dp(s1.length - 1, s2.length - 1)
}

執行起來

加入了短短幾行，差距就如此之大

然後是使用dp table的版本

有了我們之前寫的暴力遞迴的版本，就能知道dp[…][0]跟dp[0][…]就是base case，而dp[i][j]的含義跟之前的dp function類似

由於dp faunction的base case 是在i,j =-1，但是陣列的index最小也只有０，所以dp陣列會偏移一位

if (i == -1) return j + 1 //i,j其中一位是-1就是base case
if (j == -1) return i + 1

既然dp 陣列跟dp function一樣含義，就可以使用之前的想法重寫一次．但是遞迴是從結果往回求解，而Dp Table解法是從開始往結果推導

fun minDistanceWithDPTable(s1: String, s2: String): Int {
    val m = s1.length
    val n = s2.length
    val dpTable: Array<Array<Int>> = Array(m + 1) { Array(n + 1) { 0 } }
    for (i in 1 until m) {// 初始化 base case
        dpTable[i][0] = i
    }

    for (j in 1 until n) {// 初始化 base case
        dpTable[0][j] = j
    }

    for (i in 1 until m) {// 開始填滿dp Table
        for (j in 1 until n) {
            if (s1[i - 1] == s2[j - 1]) {// 相同字元不用做任何事，注意-1是因為dp table的起始
                dpTable[i][j] = dpTable[i - 1][j - 1]
            } else {
                val insert = dpTable[i][j - 1] + 1
                val delete = dpTable[i - 1][j] + 1
                val replace = dpTable[i - 1][j - 1] + 1
                dpTable[i][j] = insert.coerceAtMost(delete).coerceAtMost(replace)
            }
        }
    }
    return dpTable[m][n]
}

這題雖然是Hard，但是解法卻如此優雅，是很巧妙的設計．而且使用不同的解法，整體的執行時間可說是天差地別．另外還有一個可以優化的地方，就在這裡

//相同字元
dpTable[i][j] = dpTable[i - 1][j - 1]    
//不同字元
val insert = dpTable[i][j - 1] + 1
val delete = dpTable[i - 1][j] + 1
val replace = dpTable[i - 1][j - 1] + 1

既然每個狀態只跟這四個有關係，那我們可以進行狀態壓縮，把空間複雜度壓到 O(min(m,n))，不過這樣可讀性會降低許多，交給大家自己做看看了